package com.dmall.algorithm.chapter01;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 使用优先队列，可以将V1 版本的复杂度O(N*k) 降低为O(N*log(k))
 */
public class Leetcode239V2 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, Comparator.reverseOrder());
        for (int i = 0; i < k; i++) {
            queue.add(nums[i]);
        }

        int i = 0;
        for (; i < nums.length - k; i++) {
            Integer peek = queue.peek();
            res[i] = peek;
            queue.remove(nums[i]);
            queue.add(nums[i + k]);
        }
        res[i] = queue.peek();
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        Leetcode239V2 leetcode = new Leetcode239V2();
        int[] res = leetcode.maxSlidingWindow(nums, 3);
        System.out.println(Arrays.toString(res));
    }
}
